package a08_回溯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <p>
 * a05_电话号码的字母组合复习0
 * </p>
 *
 * @author flyduck
 * @since 2025/1/13
 */
public class a05_电话号码的字母组合复习0 {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits == null || "".equals(digits)){
            return result;
        }
        String[] photoArray = new String[]{
                "",
                "",
                "abc",
                "def",
                "ghi",
                "jkl",
                "mno",
                "pqrs",
                "tuv",
                "wxyz"
        };
        char[] chars = digits.toCharArray();
        int[] nums = new int[chars.length];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = Integer.valueOf(chars[i] + "");
        }

        LinkedList<Character> path = new LinkedList<>();
        traversal(result,path,photoArray,nums,0);
        return result;
    }

    private void traversal(List<String> result,
                           LinkedList<Character> path,
                           String[] photoArray,
                           int[] nums,
                           int numsIdx){
        if(path.size() == nums.length){
            String collect = path.stream().map(character -> character + "").collect(Collectors.joining());
            result.add(collect);
            return;
        }
        char[] chars = photoArray[nums[numsIdx]].toCharArray();
        for (int i = 0; i < chars.length; i++) {
            path.add(chars[i]);
            traversal(result, path, photoArray, nums, numsIdx + 1);
            path.removeLast();
        }
    }

}
